package leetcode.sort;

import java.util.Arrays;

/**
 * @author ：zsy
 * @date ：Created 2021/7/13 22:26
 * @description：希尔排序
 */
public class ShellSort {
    public static void main(String[] args) {
        shellSort(new int[]{8, 9, 1, 7, 2, 3, 5, 4, 6, 0});
    }

    /**
     * 原始数组：8 9 1 7 2 3 5 4 6 0
     * 第一趟排序（5）：
     *      五组: 8 3  9 5  1 4  7 6  2 0
     *      3 5 1 6 0 8 9 4 7 2
     * 第二趟排序（2）：
     *      第一组： 3 1 0 9 7 -> 0 1 3 7 9
     *      第二组： 5 6 8 4 2 -> 2 4 5 6 8
     *      0 2 1 4 3 5 7 6 9 8
     * 第三趟排序（1）：
     *      0 1 2 3 4 5 6 7 8 9
     *
     */
    public static void shellSort(int[] arr) {
        int len = arr.length;
        for (int gap = len / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < len; i++) {
                int insertIndex = i - gap;
                int insertValue = arr[i];
                while (insertIndex >= 0 && arr[insertIndex] > insertValue) {
                    arr[insertIndex + gap] = arr[insertIndex];
                    insertIndex -= gap;
                }
                if (insertIndex + gap != i) {
                    arr[insertIndex + gap] = insertValue;
                }
            }
        }
        System.out.println(Arrays.toString(arr));
    }
}
